package com.wjy.Data_Structure.graph;

import com.wjy.Data_Structure.linearlist.common.Iterator;
import com.wjy.Data_Structure.linearlist.common.LinkedList;
import com.wjy.Data_Structure.linearlist.common.Node;
import com.wjy.Data_Structure.linearlist.listslinkimpl.LinkedListDLNode;
import com.wjy.Data_Structure.queue.Queue;
import com.wjy.Data_Structure.queue.QueueSLinked;
import com.wjy.Data_Structure.stack.Stack;
import com.wjy.Data_Structure.stack.StackSLinked;

public abstract class AbstractGraph implements Graph {
	protected LinkedList vertexs;//顶点表
	protected LinkedList edges;//边表
	protected int type;// 图的类型

	public AbstractGraph(int type) {
		this.type = type;
		this.vertexs = new LinkedListDLNode();
		this.edges = new LinkedListDLNode();
	}

	@Override
	public int getType() {
		return type;
	}

	@Override
	public int getVexNum() {
		return vertexs.getSize();
	}

	@Override
	public int getEdgeNum() {
		return edges.getSize();
	}

	@Override
	public Iterator getVertex() {
		return vertexs.elements();
	}

	@Override
	public Iterator getEdge() {
		return edges.elements();
	}

	@Override
	public Node insert(Vertex v) {
		return vertexs.insertLast(v);
	}

	@Override
	public Node insert(Edge e) {
		return edges.insertLast(e);
	}

	@Override
	public boolean areAdjacent(Vertex u, Vertex v) {
		return edgeFromTo(u, v) != null;
	}

	@Override
	public Iterator DFSTraverse(Vertex v) {
		LinkedList traverseSeq = new LinkedListDLNode();//遍历结果
		resetVexStatus();//重置顶点状态
		DFS(v, traverseSeq);//从v点出发深度优先搜索
		Iterator it = getVertex(); //从图中未曾访问的其他顶点出发重新搜索
		Vertex u = null;
		for (it.first(); !it.isDone(); it.next()) {
			u = (Vertex) it.currentItem();
			if (!u.isVisited())
				DFS(u, traverseSeq);
		}
		return traverseSeq.elements();
	}

	/**
	 * 深度优先的递归算法
	 * @param v
	 * @param list
	 */
	private void DFSRecursion(Vertex v, LinkedList list) {
		v.setToVisited();
		list.insertLast(v);
		Iterator it = adjVertexs(v);//取得顶点v的所有邻接点
		Vertex u = null;
		for (it.first(); !it.isDone(); it.next()) {
			u = (Vertex) it.currentItem();
			if (!u.isVisited())
				DFSRecursion(u, list);
		}
	}

	/**
	 * 深度优先的非递归算法
	 * @param v
	 * @param list
	 */
	private void DFS(Vertex v, LinkedList list) {
		Stack s = new StackSLinked();
		s.push(v);
		Vertex u = null;
		Vertex adj = null;
		while (!s.isEmpty()) {
			u = (Vertex) s.pop();//取栈顶元素
			if (!u.isVisited()) { //如果没有访问过 
				u.setToVisited();// 访问之
				list.insertLast(u);
				Iterator it = adjVertexs(u);//未访问的邻接点入栈
				for (it.first(); !it.isDone(); it.next()) {
					adj = (Vertex) it.currentItem();
					if (!adj.isVisited())
						s.push(adj);
				}
			}
		}
	}

	@Override
	public Iterator BFSTraverse(Vertex v) {
		LinkedList traverseSeq = new LinkedListDLNode();//遍历结果
		resetVexStatus();//重置顶点的状态
		BFS(v, traverseSeq);//从v点出发广度优先搜索
		Iterator it = getVertex();//从图中未访问的顶点重新搜索
		Vertex u = null;
		for (it.first(); !it.isDone(); it.next()) {
			u = (Vertex) it.currentItem();
			if (!u.isVisited())
				BFS(u, traverseSeq);
		}
		return traverseSeq.elements();
	}

	/**
	 * 广度优先算法
	 * @param v
	 * @param list
	 */
	private void BFS(Vertex v, LinkedList list) {
		Queue q = new QueueSLinked();
		v.setToVisited(); //访问顶点v
		list.insertLast(v);
		q.enqueue(v); //顶点v入队
		Vertex u = null;
		Vertex adj = null;
		while (!q.isEmpty()) {
			u = (Vertex) q.dequeue(); //队首元素出队 
			Iterator it = adjVertexs(u); //访问其未曾访问的邻接点，并入队 
			for (it.first(); !it.isDone(); it.next()) {
				adj = (Vertex) it.currentItem();
				if (!adj.isVisited()) {
					adj.setToVisited();
					list.insertLast(adj);
					q.enqueue(adj);
				}
			}
		}
	}

	@Override
	public Iterator shortestPath(Vertex v) {
		return null;
	}

	@Override
	public void generateMST() throws UnsupportedOperation {

	}

	@Override
	public Iterator toplogicalSort() throws UnsupportedOperation {
		return null;
	}

	@Override
	public void criticalPath() throws UnsupportedOperation {

	}

	@Override
	public abstract void remove(Vertex v);

	@Override
	public abstract void remove(Edge e);

	@Override
	public abstract Edge edgeFromTo(Vertex u, Vertex v);

	@Override
	public abstract Iterator adjVertexs(Vertex u);

	//辅助方法
	/**
	 * 重置图中各顶点的状态信息
	 */
	protected void resetVexStatus() {
		Iterator it = getVertex();
		for (it.first(); !it.isDone(); it.next()) {
			Vertex u = (Vertex) it.currentItem();
			u.resetStatus();
		}

	}

	/**
	 * 重置图中个边的状态信息
	 */
	protected void resetEdgeType() {
		Iterator it = getEdge();
		for (it.first(); !it.isDone(); it.next()) {
			Edge e = (Edge) it.currentItem();
			e.resetType();
		}
	}

}
